package com.zhangxiaofanfan.hotcode.third;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;

/**
 * TODO
 *
 * @author zhangxiaofanfan
 * @date 2024-05-23 08:30:19
 */
public class HotCode009 {
    public static void main(String[] args) {
        String s = "abab";
        String p = "ab";
        HotCode009 hotCode = new HotCode009();
        System.out.println(hotCode.findAnagrams(s, p));
    }

    public List<Integer> findAnagrams(String s, String p) {
        if (s == null || p == null) {
            throw new IllegalStateException("s or p is null");
        }
        if (s.length() < p.length()) {
            return new ArrayList<>();
        }
        Map<Character, Integer> mapS = new HashMap<>();
        Map<Character, Integer> mapP = new HashMap<>();
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < p.length(); i++) {
            mapP.put(p.charAt(i), mapP.getOrDefault(p.charAt(i), 0) + 1);
            mapS.put(s.charAt(i), mapS.getOrDefault(s.charAt(i), 0) + 1);
        }
        for (int left = 0, right = left + p.length(); right < s.length(); left++, right++) {
            if (isAnagrams(mapS, mapP)) {
                result.add(left);
            }
            mapS.put(s.charAt(right), mapS.getOrDefault(s.charAt(right), 0) + 1);
            mapS.put(s.charAt(left), mapS.get(s.charAt(left)) - 1);
            if (mapS.get(s.charAt(left)) <= 0) {
                mapS.remove(s.charAt(left));
            }
        }
        return result;
    }

    public boolean isAnagrams(Map<Character, Integer> mapS, Map<Character, Integer> mapP) {
        if (mapS.size() != mapP.size()) {
            return false;
        }
        for (Character c : mapS.keySet()) {
            if (!mapP.containsKey(c)) {
                return false;
            }
            if (!mapS.get(c).equals(mapP.get(c))) {
                return false;
            }
        }
        return true;
    }
}
